package com.kehao.leetcode.hard.linkedlist;

import org.junit.Test;

import java.security.Key;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class CopyRandomListSolution {
    private class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    private Node input(Integer[][] intArray){
        Node[] nodeArray = new Node[intArray.length];
        for (int i = 0; i < nodeArray.length; i++) {
            nodeArray[i] = new Node(intArray[i][0]);
        }
        for (int i = 0; i < nodeArray.length; i++) {
            if(intArray[i][1]!=null) {
                nodeArray[i].random = nodeArray[intArray[i][1]];
            }
        }
        for (int i = 0; i < nodeArray.length - 1; i++) {
            nodeArray[i].next = nodeArray[i+1];
        }
        return nodeArray.length!=0?nodeArray[0]:null;
    }

    private void Output(Node node){
        LinkedHashMap<Node,Integer> map = new LinkedHashMap<>();
        int index = 0;
        while (node!=null){
            map.put(node,index++);
            node=node.next;
        }
        map.keySet().forEach(
                key->{
                    System.out.print("["+key.val+","+map.get(key.random)+"]");
                }
        );
        System.out.println();
    }

    public Node copyRandomList(Node head) {
        Node p1 = head;Node newHead = new Node(-1);
        Node p2 = newHead;
        HashMap<Node,Node> map = new HashMap<>();
        map.put(null,null);
        for (;p1!=null;p1=p1.next){
            p2.next = new Node(p1.val);
            p2 = p2.next;
            map.put(p1,p2);
        }
        for (p1 = head,p2=newHead.next;p1!=null;p1=p1.next,p2=p2.next){
            p2.random = map.get(p1.random);
        }

        return newHead.next;
    }

    @Test
    public void test01(){
        Integer[][] head = {{7,null},{13,0},{11,4},{10,2},{1,0}};
        Node headNode = input(head);
        Output(headNode);
        Node newHeadNode = copyRandomList(headNode);
        Output(newHeadNode);
    }

    @Test
    public void test02(){
        Integer[][] head = {{1,1},{2,1}};
        Node headNode = input(head);
        Output(headNode);
        Node newHeadNode = copyRandomList(headNode);
        Output(newHeadNode);
    }

    @Test
    public void test03(){
        Integer[][] head =  {{3,null},{3,0},{3,null}};
        Node headNode = input(head);
        Output(headNode);
        Node newHeadNode = copyRandomList(headNode);
        Output(newHeadNode);
    }

    @Test
    public void test04(){
        Integer[][] head =  {};
        Node headNode = input(head);
        Output(headNode);
        Node newHeadNode = copyRandomList(headNode);
        Output(newHeadNode);
    }
}
